#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:

    // 377. 组合总和 Ⅳ
    // https://leetcode.cn/problems/combination-sum-iv/
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();

        vector<double> dp(target+1);
        dp[0] = 1;
        for (int i = 1; i<=target; ++i)
        {
            for (int j = 0; j<n; ++j)
            {
                if (i >= nums[j])
                    dp[i] += dp[i-nums[j]];
            }
        }

        return dp[target];
    }

    // 96. 不同的二叉搜索树
    // https://leetcode.cn/problems/unique-binary-search-trees/
    int numTrees(int n) {
        vector<int> dp(n+1);
        dp[0] = 1;

        for (int i = 1; i<=n; ++i)
        {
            for (int j = 1; j<=i; ++j)
            {
                dp[i] += dp[j-1] * dp[i-j];
            }
        }

        return dp[n];
    }
};